#include<iostream>


using namespace std;

//定义节点的习惯：我总是习惯把前驱定为q，新的节点定义为p

struct ListNode {
	int val;
	ListNode* next;
	ListNode():val(0),next(NULL){}//默认构造函数
	ListNode(int x):val(x),next(NULL){}//一个参数的构造函数，值为val，后继默认为空
	ListNode(int x, ListNode* next) :val(x), next(next){}//两个参数的构造函数
};

//初始化
void InitList(ListNode* head)
{
	if (head == NULL)
		return;
	head->next = NULL;
}
//尾插
void Insert_tail(ListNode* head,int val)
{
	//创建一个新的节点newnode，并赋值为val，后继为空
	auto p = new ListNode(val);
	//找尾巴
	ListNode* q = head;//需要找前驱
	for (q = head;q->next != NULL;q = q->next)
	{
		;
	}
	//插入新的节点
	p->next = q->next;
	q->next = p;
}




//头插
void Insert_head(ListNode* head,int val)
{
	//申请一个新的节点，并初始化,赋值为val，后继为空
	auto p = new ListNode(val, head->next);//由于构造函数上面有这个定义，可以直接把第一个节点给新节点的后继
	head->next = p;//再绑住前面
}

//头删
void Del_head(ListNode* head)
{
	auto q = head->next;//保存起来
	head->next = head->next->next;
	free(q);
}


//尾删
void Del_tail(ListNode* head)
{
	ListNode*p = head;
	for (;p->next->next != NULL;p = p->next)
	{
		;
	}
	auto q = p->next;
	p->next = q->next;
	free(q);
}




//按照位置插入，在pos位置，插入数值val
void Insert_pos(ListNode* head, int val, int pos)
{
	auto p = new ListNode(val);
	int i = 0;
	auto q = head;
	for (;i < pos;q = q->next,i++)
	{
		;
	}
	//连接节点
	p->next = q->next;
	q->next = p;
}

//删除第一个val值
void Del(ListNode* head, int val)
{
	//找到第一个val值的前驱q
	ListNode* q=head;
	for (;q->next != NULL;q = q->next)
	{
		if (q->next->val == val)//q的next不为空
			break;
	}
	//先保存要删除节点的后继信息
	auto p = q->next;
	q->next = p->next;
	delete p;
}
void Show(ListNode* head)//传的是头节点
{
	for (auto p = head->next;p != NULL;p = p->next)
	{
		cout << p->val<<" ";
	}
	cout << endl;
}

int main()
{
	ListNode head;//创建一个头节点，并把他的后继置空
	//InitList(&head);
	head.next = NULL;//后继置空
	for (int i = 0;i < 10;i++)
	{
		Insert_tail(&head, i);
	}
	//Insert_head(&head, 100);
	//Insert_pos(&head, 3, 6);
	//Del(&head, 3);
	Show(&head);
	Del_head(&head);
	//Del_tail(&head);
	Show(&head);
	return 0;
}